package leetcode.p773;

import java.util.*;

/**
 * @author: trtan
 * @date: 2021-06-26 09:19
 **/
public class SlidingPuzzle {
    /**
     * bfs遍历即可
     * @param board
     * @return int
     * @author trtan
     * @date 2021/6/26 9:38
     */
    public int slidingPuzzle(int[][] board) {
        int[][] target = new int[][]{{1, 2, 3}, {4, 5, 0}};
        Queue<Node> que = new LinkedList<>();
        Map<String, Object> vis = new HashMap<>(16);
        que.offer(new Node(board, 0));
        vis.put(boardToStr(board), true);
        while (!que.isEmpty()) {
            Node node = que.poll();
            if (isSame(node.board, target)) {
                return node.cnt;
            }
            int x = 0, y = 0;
            for (int i = 0; i < node.board.length; i++) {
                for (int j = 0; j < node.board[i].length; j++) {
                    if (node.board[i][j] == 0) {
                        x = i;
                        y = j;
                        break;
                    }
                }
            }
            for (int i = -1; i <= 1; i++) {
                for (int j = -1; j <= 1; j++) {
                    if (i * j == 0) {
                        int dx = x + i;
                        int dy = y + j;
                        if (dx >= 0 && dx <= node.board[0].length && dy >= 0 && dy <= node.board.length) {
                            int[][] tmp = new int[node.board.length][node.board[0].length];
                            copyBoard(node.board, tmp);
                            int p = tmp[x][y];
                            tmp[x][y] = tmp[dx][dy];
                            tmp[dx][dy] = p;
                            String s = boardToStr(tmp);
                            if (vis.get(s) == null) {
                                que.offer(new Node(tmp, node.cnt + 1));
                                vis.put(s, true);
                            }
                        }
                    }
                }
            }
        }
        return -1;
    }

    void copyBoard(int[][] board, int[][] target) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                target[i][j] = board[i][j];
            }
        }
    }

    String boardToStr(int[][] board) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                sb.append(board[i][j]);
            }
        }
        return sb.toString();
    }

    boolean isSame(int[][] board, int[][] target) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] != target[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }

    class Node {
        int[][] board;
        int cnt;
        Node(int[][] board, int cnt) {
            this.board = board;
            this.cnt = cnt;
        }
    }
}
